struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* fast = head, * show = head;
    while (fast && fast->next)
    {
        fast = fast->next->next;
        show = show->next;

    }
    return show;
}

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* newhead = NULL;
    struct ListNode* cur = head;
    while (cur)
    {
        struct ListNode* next = cur->next;
        cur->next = newhead;
        newhead = cur;
        cur = next;



    }
    return newhead;
}
class PalindromeList {
public:
    bool chkPalindrome(ListNode* head) {
        struct ListNode* mid = middleNode(head);
        struct ListNode* rmid = reverseList(mid);
        while (rmid && head)
        {
            if (!head || !head->next)
                return true;
            if (head->val != rmid->val)
            {
                return false;
            }
            rmid = rmid->next;
            head = head->next;
        }
        return true;// write code here
    }
};